package _hash

import org.junit.Assert
import org.junit.Test

/*
https://leetcode.cn/problems/3sum/description/
https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组
注意：答案中不可以包含重复的三元组。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

输入：nums = [0,1,1]
输出：[]

输入：nums = [0,0,0]
输出：[[0,0,0]]
 */
class leetcode_15 {
    @Test
    fun test_1() {
        val actual = threeSum(intArrayOf(-1, 0, 1, 2, -1, -4))
        val expect = listOf(listOf(-1, -1, 2), listOf(-1, 0, 1))
        Assert.assertEquals(actual.joinToString(), expect.joinToString())
    }

    @Test
    fun test_2() {
        val actual = threeSum(intArrayOf(0, 1, 1))
        val expect: List<List<Int>> = listOf()
        Assert.assertEquals(actual.joinToString(), expect.joinToString())
    }

    @Test
    fun test_3() {
        val actual = threeSum(intArrayOf(0, 0, 0))
        val expect: List<List<Int>> = listOf(listOf(0, 0, 0))
        Assert.assertEquals(actual.joinToString(), expect.joinToString())
    }

    /**
     * 排序 + 双指针
     * 本题的难点在于如何去除重复解。
     *
     * 算法流程：
     * 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
     * 对数组进行排序。
     * 遍历排序后数组：
     * 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
     * 对于重复元素：跳过，避免出现重复解
     * 令左指针 L=i+1，右指针 R=n−1，当 L<R 时，执行循环：
     * 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
     * 若和大于 0，说明 nums[R] 太大，R 左移
     * 若和小于 0，说明 nums[L] 太小，L 右移
     *
     * 链接：https://leetcode.cn/problems/3sum/solutions/39722/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/
     *
     */
    fun threeSum(nums: IntArray): List<List<Int>> {
        /**
        先排序
        双指针方法
        去重复a b c
        i == i-1
        left == left + 1, left++
        right == right -1, right--
         */
        // T - N * N
        // S - N
        nums.sort() // 从小到大
        val end = nums.size - 1
        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        var left: Int
        var right: Int
        var sum: Int
        for (i in 0..end) {
            // 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
            if (nums[i] > 0) {
                return result
            }
            // 对于重复元素：跳过，避免出现重复解
            if (i - 1 >= 0 && nums[i] == nums[i - 1]) {
                continue
            }
            left = i + 1
            right = end

            while (right > left) {
                sum = nums[i] + nums[left] + nums[right]
                if (sum < 0) {
                    left++
                } else if (sum == 0) {
                    result.add(arrayListOf(nums[i], nums[left], nums[right]))
                    // 去重 right
                    while (right > left && nums[right] == nums[right - 1]) right--
                    // 去重 left
                    while (right > left && nums[left] == nums[left + 1]) left++
                    right--
                    left++
                } else {
                    right--
                }
            }
        }
        return result
    }
}